package _binary_tree

import common.v1.Node
import org.junit.Assert
import org.junit.Test
import java.util.*
import kotlin.collections.ArrayList

/*
  589. N 叉树的前序遍历
  示例 1：
  输入：root = [1,null,3,2,4,null,5,6]
  输出：[1,3,5,6,2,4]

    示例 2：
    输入：root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
    输出：[1,2,3,6,7,11,14,4,8,12,5,9,13,10]
 */
class leetcode_589 {
    @Test
    fun test_1() {
        val root = Node(1)
        val n2 = Node(2)
        val n3 = Node(3)
        val n4 = Node(4)
        val n5 = Node(5)
        val n6 = Node(6)
        root.children = arrayListOf(n3, n2, n4)
        n3.children = arrayListOf(n5, n6)
        val actual = preorder(root)
        val expect = arrayListOf(1, 3, 5, 6, 2, 4)
        Assert.assertEquals(expect.toString(), actual.toString())
    }


    @Test
    fun test_2() {
        val root = Node(1)
        val n2 = Node(2)
        val n3 = Node(3)
        val n4 = Node(4)
        val n5 = Node(5)
        val n6 = Node(6)
        val n7 = Node(7)
        val n8 = Node(8)
        val n9 = Node(9)
        val n10 = Node(10)
        val n11 = Node(11)
        val n12 = Node(12)
        val n13 = Node(13)
        val n14 = Node(14)
        root.children = arrayListOf(n2, n3, n4, n5)
        n3.children = arrayListOf(n6, n7)
        n4.children = arrayListOf(n8)
        n5.children = arrayListOf(n9, n10)
        n7.children = arrayListOf(n11)
        n8.children = arrayListOf(n12)
        n9.children = arrayListOf(n13)
        n11.children = arrayListOf(n14)

        val actual = preorder(root)
        val expect: ArrayList<Int> = arrayListOf(1, 2, 3, 6, 7, 11, 14, 4, 8, 12, 5, 9, 13, 10)
        Assert.assertEquals(expect.toString(), actual.toString())
    }

    private fun preorder(root: Node?): List<Int> {
        val result: ArrayList<Int> = ArrayList<Int>()
        // preorder1(root,result)
//        preorder2(root, result)
        preorder3(root, result)
        return result
    }

    // 深度遍历 - 前序 - 递归
    private fun preorder1(root: Node?, result: ArrayList<Int>) {
        // S - N
        // T - N
        if (null == root) {
            return
        }
        result.add(root.`val`)
        for (child in root.children) {
            preorder1(child, result)
        }
    }

    // 深度遍历 - 前序 - 迭代
    private fun preorder2(root: Node?, result: ArrayList<Int>) {
        // S - N
        // T - N
        if (null == root) {
            return
        }
        val stack: LinkedList<Node> = LinkedList<Node>()
        stack.push(root)
        while (!stack.isEmpty()) {
            val node = stack.pop()
            result.add(node.`val`)
            val size = node.children.size;
            if (size >= 1) {
                for (i in size - 1 downTo 0) {
                    stack.push(node.children.get(i))
                }
            }
        }
    }

    // 深度遍历 - 前序 - 迭代(统一写法)
    private fun preorder3(root: Node?, result: ArrayList<Int>) {
        // S - N
        // T - N
        // 1 终止条件
        if (null == root) {
            return
        }

        // 2 初始化栈
        val stack: LinkedList<Pair<Node, Boolean>> = LinkedList<Pair<Node, Boolean>>()
        stack.push(Pair<Node, Boolean>(root, false))

        // 3 利用栈遍历节点
        while (!stack.isEmpty()) {
            val pair: Pair<Node, Boolean> = stack.pop()
            val node = pair.first
            val visited = pair.second

            // 收集节点
            if (visited) {
                result.add(node.`val`)
                continue
            }
            // 处理逻辑：前序遍历
            // 栈：N...1, node
            val size = node.children.size;
            if (size >= 1) {
                for (i in size - 1 downTo 0) { // TODO:downTo
                    node.children[i]?.let {
                        stack.push(Pair<Node, Boolean>(it, false))
                    }
                }
            }
            stack.push(Pair<Node, Boolean>(node, true))
        }
    }
}